package com.hy.study.sparsearray;

import java.util.Arrays;

/**
 * 原始数组转换为 稀疏数组
 * 例如 五子棋
 */
public class SparseArray {
    public static void main(String[] args) {
        //创建一个二维数组
        //0：表示没有棋子 1 表示黑子  2 表示蓝子
        int[][] chessArr1 = new int[11][11];
        chessArr1[1][2]=1;
        chessArr1[2][3]=2;
        System.out.println("原始的二位数组:");
        for (int[] row: chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
        // 这里将0 看作是无效数据
        //表示多少个有效数据
        int sum=0;
        for(int i=0;i<chessArr1.length;i++){
            for(int j=0;j<chessArr1[i].length;j++){
              int temp=  chessArr1[i][j];
              if(temp!=0){
                  sum++;
              }
            }
        }
        System.out.println(sum);

        //创建稀疏数组 稀疏数组的行 是有效数据个数+1(第一行中表示 原始数据的信息  ) 列是固定的3
        // 第一行记录 用来记录原始数组的信息，第一行第一列 表示原始数组的行数，第一行第二列表示原始数组的列数，第一行第三列表示原始数组中有效数据的个数。
        int sparseArr[][]=new int[sum+1][3];
        sparseArr[0][0]=chessArr1.length;
        sparseArr[0][1]=chessArr1[0].length;
        sparseArr[0][2]=sum;
        //遍历二位数组 将非0 的值存放到稀疏数组中
        int count=0;//用于记录是第几个非零数据
        for(int i=0;i<chessArr1.length;i++){
            for(int j=0;j<chessArr1[i].length;j++){
                int temp=  chessArr1[i][j];
                if(temp!=0){
                    count++;//这里需要先加 因为 第一行一次存放了其他的信息
                    sparseArr[count][0]=i;
                    sparseArr[count][1]=j;
                    sparseArr[count][2]=temp;
                }
            }
        }
        //输出稀疏数组
        System.out.println();
        System.out.println("=============得到的稀疏数组=============");
        for (int i = 0; i < sparseArr.length; i++) {
            int[] sparse = sparseArr[i];
            for (int j = 0; j < sparse.length; j++) {
                int value = sparse[j];
                System.out.printf("%d\t",value);
            }
            System.out.println();

        }
        System.out.println();
        // 将稀疏数组恢复成 二位数组
        System.out.println();
        //根据稀疏数组 得到一个二位数组
        int [][] resultArr=  new int[sparseArr[0][0]][sparseArr[0][1]];
        //从稀疏数组的第二行开始
        for (int i = 1; i < sparseArr.length; i++) {
            int[] sparse = sparseArr[i];
            resultArr[sparse[0]][sparse[1]]=sparse[2];
        }
        //遍历恢复后的正常数据
        System.out.println("=============通过稀疏数组恢复后的数组=============");
        for (int[] row: resultArr) {
            for (int data : row) {
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
    }
}
